#include <stdio.h>
#include <stdlib.h>

#define LIST_INIT_SIZE 100  //线性表存储空间的初始分配量
#define LISTINCREMENT 10    //线性表存储空间的分配增量
#define ElemType int    //线性表元素类型定义
#define OK 1    //操作成功
#define ERROR 0 //操作失败

typedef struct
{
    ElemType *elem; //存储空间基址
    int length; //线性表当前长度
    int listsize;   //线性表当前分配的存储容量
} SqList;

int InitList_Sq(SqList *L)  //构造一个空的线性表L
{
    L->elem = (ElemType *)malloc(LIST_INIT_SIZE * sizeof(ElemType));//为线性表分配初始存储空间
    if (L->elem == NULL)    //存储分配失败
    {
        return ERROR;   //返回失败标志
    }
    L->length = 0;  //空表长度为0
    L->listsize = LIST_INIT_SIZE;   //初始存储容量
    return OK;  //返回成功标志
}

/* 在位置 i (1-based) 插入元素 e */
int ListInsert(SqList *L, int i, ElemType e)
{
    if (L == NULL) return ERROR;
    if (i < 1 || i > L->length + 1) return ERROR; /* 检查插入位置合法性 */

    /* 若当前存储空间已满，则增加分配 */
    if (L->length >= L->listsize) {
        ElemType *newbase = (ElemType *)realloc(L->elem, (L->listsize + LISTINCREMENT) * sizeof(ElemType));
        if (newbase == NULL) return ERROR;
        L->elem = newbase;
        L->listsize += LISTINCREMENT;
    }

    /* 将插入位置及之后元素后移一位（使用下标，避免指针边界问题） */
    for (int k = L->length - 1; k >= i - 1; --k) {
        L->elem[k + 1] = L->elem[k];
    }

    L->elem[i - 1] = e; /* 在位置 i-1 存放新元素 */
    L->length++;
    return OK;
}

/* 打印顺序表内容（元素索引从 1 开始显示） */
void PrintList(const SqList *L)
{
    if (L == NULL) return;
    printf("SqList length=%d, listsize=%d\n", L->length, L->listsize);
    for (int i = 0; i < L->length; ++i) {
        printf("L[%d]=%d\n", i + 1, L->elem[i]);
    }
}

/* 释放顺序表占用的存储 */
void DestroyList(SqList *L)
{
    if (L == NULL) return;
    if (L->elem != NULL) free(L->elem);
    L->elem = NULL;
    L->length = 0;
    L->listsize = 0;
}

/* 测试：在已有数组 10,20,30,40,50 中插入 25（保持有序） */
int main(void)
{
    SqList L;
    if (InitList_Sq(&L) == ERROR) {
        fprintf(stderr, "InitList_Sq failed\n");
        return 1;
    }

    /* 直接赋初值为 10,20,30,40,50 */
    int init_vals[] = {10, 20, 30, 40, 50};
    int n = sizeof(init_vals) / sizeof(init_vals[0]);
    for (int i = 0; i < n; ++i) {
        L.elem[i] = init_vals[i];
    }
    L.length = n;

    printf("初始顺序表：\n");
    PrintList(&L);

    /* 要插入的值 */
    ElemType value = 25;

    /* 自动查找插入位置以保持升序（插入到第一个大于 value 的元素之前） */
    int pos = L.length + 1; /* 默认插入到末尾 */
    for (int i = 0; i < L.length; ++i) {
        if (L.elem[i] > value) {
            pos = i + 1; /* 1-based 位置 */
            break;
        }
    }

    if (ListInsert(&L, pos, value) == OK) {
        printf("在位置 %d 插入 %d 后：\n", pos, value);
        PrintList(&L);
    } else {
        printf("插入 %d 失败\n", value);
    }

    DestroyList(&L);
    return 0;
}
